#include "sclinkedlist.h"


//初始化
void InitScLinkedList(List *list)
{
    //申请结点
    Node *s = NODE;
    assert(s != NULL);
    //将链表管理结点中的头指针和尾指针分别指向这个结点
    list->first = list->last = s;
    //将尾结点的下一个结点指向头结点形成循环
    list->last->next = list->first;
    list->size = 0;
}

//尾插法
void scLinkedList_push_back(List *list, ElemType x)
{
    Node *s = _buynode(x); //利用X申请一个要插入的结点
    list->last->next = s;
    list->last = s;
    list->last->next = list->first; //重新指向头结点
    list->size++; //将有效结点+1
}

//头插法
void scLinkedList_push_front(List *list, ElemType x)
{
    Node *s = _buynode(x);
    s->next = list->first->next;
    list->first->next = s;
    //如果这是一个有效结点，那么需要更改管理结点中尾指针的指向
    if (list->first == list->last)
    {
        list->last = s;
    }
    list->size++;
}

//数据显示
void scLinkedList_show_list(List *list)
{
    Node *p = list->first->next; //指向有效结点的指针
    while (p != list->first)
    {
        printf("%d-->", p->data);
        p = p->next; //下移
    }
    printf("Nul. \n");
}

//尾删除1
void scLinkedList_pop_back(List *list)
{
    if (list->size == 0)
    {
        return;
    }
    Node *p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    free(list->last); //删除尾结点
    list->last = p;
    list->last->next = list->first; //重新形成环
    list->size--;
}

//头删除
void scLinkedList_pop_front(List *list)
{
    if (list->size == 0)
    {
        return;
    }
    Node *p = list->first->next;  //有准备头结点
    list->first->next = p->next;
    free(p);
    if (list->size == 1)
    {
        list->last = list->first;
    }
    list->size--;
}

//按值插入 按照升序插入
void scLinkedList_insert_val(List *list, ElemType x)
{
    Node *p = list->first;
    while (p->next != list->last && p->next->data != x)
    {
        p = p->next;
    }
    //如果插入在尾部
    if (p->next == list->last && p->next->data < x)
    {
        scLinkedList_push_back(list, x);
    }
        //中间插入
    else
    {
        Node *s = _buynode(x);
        s->next = p->next;
        p->next = s;
        list->size++;
    }

}

//按值查找
Node *scLinkedList_find(List *list, ElemType x)
{
    if (list->size == 0)
    {
        return NULL;
    }
    //从有效的首结点开始查找
    Node *p = list->first->next;
    while (p != list->first && p->data != x)
    {
        p = p->next;
    }
    if (p == list->first)
    {
        return NULL;
    }
    return p;
}

//结点个数
int scLinkedList_length(List *list)
{
    return list->size;
}

//按值删除
void scLinkedList_delete_val(List *list, ElemType x)
{
    if (list->size == 0)
    {
        return;
    }
    Node *p = scLinkedList_find(list, x);
    if (p == NULL)
    {
        printf("not found be deleted data. \n");
        return;
    }
    if (p == list->last)
    {
        scLinkedList_pop_back(list);
    } else
    {
        Node *q = p->next;
        p->data = q->data;
        p->next = q->next;
        free(q);
        list->size--;
    }

}

//排序(升序)
void scLinkedList_sort(List *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    Node *s = list->first->next;  //有效的每一个结点
    Node *q = s->next;  //第二个结点
    //将原有的链断开,形成一个只含一个有效结点的循环链表和一个单链表
    list->last->next = NULL; //单链表的尾结点指向空
    list->last = s;
    list->last->next = list->first;

    while (q != NULL)
    {//将单链表内的有效结点逐一按照值插入方式（升序的值插入）插入到循环链表中
        //从单链表中拿下一下有效结点
        s = q;
        q = q->next;

        Node *p = list->first;
        while (p->next != list->last && p->next->data < s->data)
        {
            p = p->next;
        }
        if (p->next == list->last && p->next->data < s->data)
        {
            s->next = list->last->next;
            list->last->next = s;
            list->last = s;
        } else
        {
            s->next = p->next;
            p->next = s;
        }
    }


}

//倒置
void scLinkedList_resver(List *list)
{
    //判断是否要进行逆置（有效结点数小于等于1个不进行逆置）
    if (list->size == 0 || list->size == 1)
        return;
    Node *p = list->first->next; //指向第一个结点
    Node *q = p->next; //指向每2个结点
    //将原来的循环链表断开，形成一个只含一个有效结点的循环链表和一个单链表
    list->last->next = NULL;  //去掉闭环
    list->last = p; //将第一个结点赋值给末尾结点
    list->last->next = list->first; //重新形成闭环

    while (q != NULL)
    {
        p = q;
        q = p->next;
        //
        p->next = list->first->next;
        list->first->next = p;
    }


}

//清空结点
void scLinkedList_clear(List *list)
{
    Node *p = list->first->next;
    while (p != list->first)
    {
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    //设置管理结点中的尾结点指向和头结点的指针域指向
    list->last = list->first;
    list->last->next = list->first;
    list->size = 0;
}

//销毁
void scLinkedList_destory(List *list)
{
    scLinkedList_clear(list);
    free(list->first);
    list->first = list->last = NULL;
}